home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / text / tex / tgrind.lha / TGrind / regexp.c < prev    next >
C/C++ Source or Header  |  1993-01-04  |  14KB  |  596 lines
  1. #ifndef lint
  2. static char *sccsid="@(#)regexp.c    1.2 (LBL) 4/12/85";
  3. #endif
  4. /*
  5.  * regular expression matching routines for tgrind/tfontedpr.
  6.  *
  7.  * These routines were written by Dave Presotto (I think) for vgrind.
  8.  * Minor mods & attempts to improve performance by Van Jacobson (van@lbl-rtsg)
  9.  * and Chris Torek (chris@maryland).
  10.  *
  11.  * Modifications.
  12.  * --------------
  13.  * 30Mar85 Van & Chris    Changed expmatch to return pointer to start of what
  14.  *            was matched in addition to pointer to match end.
  15.  *            Several changes to improve performance (too numerous
  16.  *            to mention).
  17.  * 11Dec84 Dave Presotto  Written.
  18.  */
  19.  
  20. #include <ctype.h>
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24.  
  25. #ifndef boolean
  26. typedef int    boolean;
  27. #define TRUE    1
  28. #define FALSE    0
  29. #endif
  30. #define NIL    0
  31.  
  32. #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
  33.  
  34. extern int    (*re_strncmp)(char *, char *, size_t);    /* function used by expmatch to compare
  35.                  * strings.  The caller should make it point to
  36.                  * strncmp if case is significant &
  37.                  * lc_strncmp otherwise.
  38.                  */
  39. void expconv(void);
  40.  
  41. /*  lc_strncmp - like strncmp except that we convert the
  42.  *         first string to lower case before comparing.
  43.  */
  44.  
  45. int lc_strncmp(char *s1, char *s2, size_t len)
  46. {
  47.     while (len-- > 0)
  48.         if (*s2 - makelower(*s1))
  49.             return(1);
  50.         else
  51.         s2++, s1++;
  52.  
  53.     return(0);
  54. }
  55.  
  56. /*    The following routine converts an irregular expression to
  57.  *    internal format.
  58.  *
  59.  *    Either meta symbols (\a \d or \p) or character strings or
  60.  *    operations ( alternation or perenthesizing ) can be
  61.  *    specified.  Each starts with a descriptor byte.  The descriptor
  62.  *    byte has STR set for strings, META set for meta symbols
  63.  *    and OPER set for operations.
  64.  *    The descriptor byte can also have the OPT bit set if the object
  65.  *    defined is optional.  Also ALT can be set to indicate an alternation.
  66.  *
  67.  *    For metasymbols the byte following the descriptor byte identities
  68.  *    the meta symbol (containing an ascii 'a', 'd', 'p', '|', or '(').  For
  69.  *    strings the byte after the descriptor is a character count for
  70.  *    the string:
  71.  *
  72.  *        meta symbols := descriptor
  73.  *                symbol
  74.  *
  75.  *        strings :=    descriptor
  76.  *                character count
  77.  *                the string
  78.  *
  79.  *        operatins :=    descriptor
  80.  *                symbol
  81.  *                character count
  82.  */
  83.  
  84. /*
  85.  *  handy macros for accessing parts of match blocks
  86.  */
  87. #define MSYM(A) (*(A+1))    /* symbol in a meta symbol block */
  88. #define MNEXT(A) (A+2)        /* character following a metasymbol block */
  89.  
  90. #define OSYM(A) (*(A+1))    /* symbol in an operation block */
  91. #define OCNT(A) (*(A+2))    /* character count */
  92. #define ONEXT(A) (A+3)        /* next character after the operation */
  93. #define OPTR(A) (A+*(A+2))    /* place pointed to by the operator */
  94.  
  95. #define SCNT(A) (*(A+1))    /* byte count of a string */
  96. #define SSTR(A) (A+2)        /* address of the string */
  97. #define SNEXT(A) (A+2+*(A+1))    /* character following the string */
  98.  
  99. /*
  100.  *  bit flags in the descriptor
  101.  */
  102. #define OPT 1
  103. #define STR 2
  104. #define META 4
  105. #define ALT 8
  106. #define OPER 16
  107.  
  108. char *ure;        /* pointer current position in unconverted exp */
  109. char *ccre;        /* pointer to current position in converted exp*/
  110.  
  111. char * convexp(char *re)    /* unconverted irregular expression */
  112. {
  113.     register char *cre;        /* pointer to converted regular expression */
  114.  
  115.     /* allocate room for the converted expression */
  116.     if (re == NIL)
  117.     return (NIL);
  118.     if (*re == '\0')
  119.     return (NIL);
  120.     cre = malloc (4 * strlen(re) + 3);
  121.     ccre = cre;
  122.     ure = re;
  123.  
  124.     /* start the conversion with a \a */
  125.     *cre = META | OPT;
  126.     MSYM(cre) = 'a';
  127.     ccre = MNEXT(cre);
  128.  
  129.     /* start the conversion (its recursive) */
  130.     expconv ();
  131.     *ccre = 0;
  132.     return (cre);
  133. }
  134.  
  135. void expconv(void)
  136. {
  137.     register char *cs;        /* pointer to current symbol in converted exp */
  138.     register char c;        /* character being processed */
  139.     register char *acs;        /* pinter to last alternate */
  140.     register int temp;
  141.  
  142.     /* let the conversion begin */
  143.     acs = NIL;
  144.     cs = NIL;
  145.     while (*ure != NIL) {
  146.     switch (c = *ure++) {
  147.  
  148.     case '\\':
  149.         switch (c = *ure++) {
  150.  
  151.         /* escaped characters are just characters */
  152.         default:
  153.         if (cs == NIL || (*cs & STR) == 0) {
  154.             cs = ccre;
  155.             *cs = STR;
  156.             SCNT(cs) = 1;
  157.             ccre += 2;
  158.         } else
  159.             SCNT(cs)++;
  160.         *ccre++ = c;
  161.         break;
  162.  
  163.         /* normal(?) metacharacters */
  164.         case 'a':
  165.         case 'd':
  166.         case 'e':
  167.         case 'p':
  168.         if (acs != NIL && acs != cs) {
  169.             do {
  170.             temp = OCNT(acs);
  171.             OCNT(acs) = ccre - acs;
  172.             acs -= temp;
  173.             } while (temp != 0);
  174.             acs = NIL;
  175.         }
  176.         cs = ccre;
  177.         *cs = META;
  178.         MSYM(cs) = c;
  179.         ccre = MNEXT(cs);
  180.         break;
  181.         }
  182.         break;
  183.  
  184.     /* just put the symbol in */
  185.     case '^':
  186.     case '$':
  187.         if (acs != NIL && acs != cs) {
  188.         do {
  189.             temp = OCNT(acs);
  190.             OCNT(acs) = ccre - acs;
  191.             acs -= temp;
  192.         } while (temp != 0);
  193.         acs = NIL;
  194.         }
  195.         cs = ccre;
  196.         *cs = META;
  197.         MSYM(cs) = c;
  198.         ccre = MNEXT(cs);
  199.         break;
  200.  
  201.     /* mark the last match sequence as optional */
  202.     case '?':
  203.         if (cs)
  204.             *cs = *cs | OPT;
  205.         break;
  206.  
  207.     /* recurse and define a subexpression */
  208.     case '(':
  209.         if (acs != NIL && acs != cs) {
  210.         do {
  211.             temp = OCNT(acs);
  212.             OCNT(acs) = ccre - acs;
  213.             acs -= temp;
  214.         } while (temp != 0);
  215.         acs = NIL;
  216.         }
  217.         cs = ccre;
  218.         *cs = OPER;
  219.         OSYM(cs) = '(';
  220.         ccre = ONEXT(cs);
  221.         expconv ();
  222.         OCNT(cs) = ccre - cs;        /* offset to next symbol */
  223.         break;
  224.  
  225.     /* return from a recursion */
  226.     case ')':
  227.         if (acs != NIL) {
  228.         do {
  229.             temp = OCNT(acs);
  230.             OCNT(acs) = ccre - acs;
  231.             acs -= temp;
  232.         } while (temp != 0);
  233.         acs = NIL;
  234.         }
  235.         cs = ccre;
  236.         *cs = META;
  237.         MSYM(cs) = c;
  238.         ccre = MNEXT(cs);
  239.         return;
  240.  
  241.     /* mark the last match sequence as having an alternate */
  242.     /* the third byte will contain an offset to jump over the */
  243.     /* alternate match in case the first did not fail */
  244.     case '|':
  245.         if (acs != NIL && acs != cs)
  246.         OCNT(ccre) = ccre - acs;    /* make a back pointer */
  247.         else
  248.         OCNT(ccre) = 0;
  249.         *cs |= ALT;
  250.         cs = ccre;
  251.         *cs = OPER;
  252.         OSYM(cs) = '|';
  253.         ccre = ONEXT(cs);
  254.         acs = cs;    /* remember that the pointer is to be filles */
  255.         break;
  256.  
  257.     /* if its not a metasymbol just build a scharacter string */
  258.     default:
  259.         if (cs == NIL || (*cs & STR) == 0) {
  260.         cs = ccre;
  261.         *cs = STR;
  262.         SCNT(cs) = 1;
  263.         ccre = SSTR(cs);
  264.         } else
  265.         SCNT(cs)++;
  266.         *ccre++ = c;
  267.         break;
  268.     }
  269.     }
  270.     if (acs != NIL) {
  271.     do {
  272.         temp = OCNT(acs);
  273.         OCNT(acs) = ccre - acs;
  274.         acs -= temp;
  275.     } while (temp != 0);
  276.     acs = NIL;
  277.     }
  278.     return;
  279. }
  280. /* end of convertre */
  281.  
  282.  
  283. /*
  284.  *    The following routine recognises an irregular expresion
  285.  *    with the following special characters:
  286.  *
  287.  *        \?    -    means last match was optional
  288.  *        \a    -    matches any number of characters
  289.  *        \d    -    matches any number of spaces and tabs
  290.  *        \p    -    matches any number of alphanumeric
  291.  *                characters. The
  292.  *                characters matched will be copied into
  293.  *                the area pointed to by 'name'.
  294.  *        \|    -    alternation
  295.  *        \( \)    -    grouping used mostly for alternation and
  296.  *                optionality
  297.  *
  298.  *    The irregular expression must be translated to internal form
  299.  *    prior to calling this routine
  300.  *
  301.  *    The value returned is the pointer to the last character matched.
  302.  *    If strtptr is non-null, a pointer to the start of the string matched
  303.  *    (excluding \a matches) will be returned at *strtptr.
  304.  *    If mstring is non-null, the string matched by a \p will be copied
  305.  *    into mstring.
  306.  */
  307.  
  308. boolean _escaped;        /* true if we are currently _escaped */
  309. char *_start;            /* start of string */
  310.  
  311. char *expmatch (char *s, char *re, char **strtptr, char *mstring)
  312. /*    register char *s;        string to check for a match in */
  313. /*    register char *re;        a converted irregular expression */
  314. /*    char **strtptr;         where to put ptr to start of match */
  315. /*    char *mstring;         where to put whatever matches a \p */
  316. {
  317.     register char *cs;        /* the current symbol */
  318.     register char *ptr, *s1;    /* temporary pointer */
  319.     register char c;        /* temporary */
  320.     boolean matched;        /* a temporary boolean */
  321.  
  322.     /* initial conditions */
  323.     if ( strtptr )
  324.     *strtptr = NIL;
  325.     if (re == NIL)
  326.     return (NIL);
  327.     cs = re;
  328.     matched = FALSE;
  329.  
  330.     /* loop till expression string is exhausted (or at least pretty tired) */
  331.     while (*cs) {
  332.     switch (*cs & (OPER | STR | META)) {
  333.  
  334.     /* try to match a string */
  335.     case STR:
  336.         matched = !((*re_strncmp)(s, SSTR(cs), SCNT(cs)));
  337.         if (matched) {
  338.  
  339.         /* hoorah it matches */
  340.         s += SCNT(cs);
  341.         cs = SNEXT(cs);
  342.         } else if (*cs & ALT) {
  343.  
  344.         /* alternation, skip to next expression */
  345.         cs = SNEXT(cs);
  346.         } else if (*cs & OPT) {
  347.  
  348.         /* the match is optional */
  349.         cs = SNEXT(cs);
  350.         matched = 1;        /* indicate a successful match */
  351.         } else {
  352.  
  353.         /* no match, error return */
  354.         return (NIL);
  355.         }
  356.         break;
  357.  
  358.     /* an operator, do something fancy */
  359.     case OPER:
  360.         switch (OSYM(cs)) {
  361.  
  362.         /* this is an alternation */
  363.         case '|':
  364.         if (matched)
  365.  
  366.             /* last thing in the alternation was a match, skip ahead */
  367.             cs = OPTR(cs);
  368.         else
  369.  
  370.             /* no match, keep trying */
  371.             cs = ONEXT(cs);
  372.         break;
  373.  
  374.         /* this is a grouping, recurse */
  375.         case '(':
  376.         ptr = expmatch (s, ONEXT(cs), strtptr, mstring);
  377.         if (ptr != NIL) {
  378.  
  379.             /* the subexpression matched */
  380.             matched = 1;
  381.             s = ptr;
  382.         } else if (*cs & ALT) {
  383.  
  384.             /* alternation, skip to next expression */
  385.             matched = 0;
  386.         } else if (*cs & OPT) {
  387.  
  388.             /* the match is optional */
  389.             matched = 1;    /* indicate a successful match */
  390.         } else {
  391.  
  392.             /* no match, error return */
  393.             return (NIL);
  394.         }
  395.         cs = OPTR(cs);
  396.         break;
  397.         }
  398.         break;
  399.  
  400.     /* try to match a metasymbol */
  401.     case META:
  402.         switch (MSYM(cs)) {
  403.  
  404.         /* try to match anything and remember what was matched */
  405.         case 'p':
  406.         /*
  407.          *  This is really the same as trying the match the
  408.          *  remaining parts of the expression to any subset
  409.          *  of the string.
  410.          */
  411.         s1 = s;
  412.         do {
  413.             ptr = expmatch (s1, MNEXT(cs), strtptr, mstring);
  414.             if (ptr != NIL && s1 != s) {
  415.  
  416.             /* we have a match, remember the match */
  417.             if ( mstring ) {
  418.                 strncpy (mstring, s, s1 - s);
  419.                 mstring[s1 - s] = '\0';
  420.             }
  421.             return (ptr);
  422.  
  423.             } else if (ptr != NIL && (*cs & OPT)) {
  424.  
  425.             /* \p was optional so no match is ok */
  426.             return (ptr);
  427.  
  428.             } else if (ptr != NIL) {
  429.  
  430.             /* not optional and we still matched */
  431.             return (NIL);
  432.             }
  433.             if (!isalnum(*s1) && *s1 != '_')
  434.             return (NIL);
  435.             if (*s1 == '\\')
  436.             _escaped = _escaped ? FALSE : TRUE;
  437.             else
  438.             _escaped = FALSE;
  439.         } while (*s1++);
  440.         return (NIL);
  441.  
  442.         /* try to match anything */
  443.         case 'a':
  444.         /*
  445.          *  This is really the same as trying the match the
  446.          *  remaining parts of the expression to any subset
  447.          *  of the string.
  448.          */
  449.         s1 = s;
  450.         do {
  451.             /*
  452.              * Hack for an important special case:  if the next thing
  453.              * in the pattern is a string, just gobble characters until
  454.              * we find something that matches that string (this saves
  455.              * the cost of a recursive call on expmatch while scanning
  456.              * for the start of comments or strings).  Since many
  457.              * patterns end with a string, we also treat that as a
  458.              * special case.
  459.              */
  460.             if( *(ptr=MNEXT(cs)) == STR ) {
  461.             c = *SSTR(ptr);
  462.             while( *s1 && *s1 != c )
  463.                 s1++;
  464.  
  465.             if ( *s1 == 0 )
  466.                 return(NIL);
  467.  
  468.             if ( SNEXT(ptr) == 0 && (s1 != s || *cs & OPT)) {
  469.                 /* next item is a string, it's the last item and
  470.                  * the \a match is ok - just loop to try & match
  471.                  * the string.
  472.                  */
  473.                 if ( strtptr )
  474.                 *strtptr = s1;
  475.  
  476.                 cs = ptr;
  477.                 s = s1;
  478.                 break;
  479.             }
  480.             }
  481.             ptr = expmatch (s1, MNEXT(cs), strtptr, mstring);
  482.             if (ptr != NIL && (s1 != s || *cs & OPT)) {
  483.  
  484.             /* we have a match */
  485.             if ( strtptr )
  486.                 *strtptr = s1;
  487.  
  488.             return(ptr);
  489.  
  490.             } else if (ptr != NIL) {
  491.  
  492.             /* not optional and we still matched */
  493.             return (NIL);
  494.             }
  495.             if (*s1 == '\\')
  496.             _escaped = _escaped ? FALSE : TRUE;
  497.             else
  498.             _escaped = FALSE;
  499.         } while (*s1++);
  500.         return (NIL);
  501.  
  502.         /* fail if we are currently _escaped */
  503.         case 'e':
  504.         if (_escaped)
  505.             return(NIL);
  506.         cs = MNEXT(cs);
  507.         break;
  508.  
  509.         /* match any number of tabs and spaces */
  510.         case 'd':
  511.         ptr = s;
  512.         while (*s == ' ' || *s == '\t')
  513.             s++;
  514.         if (s != ptr || s == _start) {
  515.  
  516.             /* match, be happy */
  517.             matched = 1;
  518.             cs = MNEXT(cs);
  519.         } else if (*s == '\n' || *s == '\0') {
  520.  
  521.             /* match, be happy */
  522.             matched = 1;
  523.             cs = MNEXT(cs);
  524.         } else if (*cs & ALT) {
  525.  
  526.             /* try the next part */
  527.             matched = 0;
  528.             cs = MNEXT(cs);
  529.         } else if (*cs & OPT) {
  530.  
  531.             /* doesn't matter */
  532.             matched = 1;
  533.             cs = MNEXT(cs);
  534.         } else
  535.  
  536.             /* no match, error return */
  537.             return (NIL);
  538.         break;
  539.  
  540.         /* check for end of line */
  541.         case '$':
  542.         if (*s == '\0' || *s == '\n') {
  543.  
  544.             /* match, be happy */
  545.             s++;
  546.             matched = 1;
  547.             cs = MNEXT(cs);
  548.         } else if (*cs & ALT) {
  549.  
  550.             /* try the next part */
  551.             matched = 0;
  552.             cs = MNEXT(cs);
  553.         } else if (*cs & OPT) {
  554.  
  555.             /* doesn't matter */
  556.             matched = 1;
  557.             cs = MNEXT(cs);
  558.         } else
  559.  
  560.             /* no match, error return */
  561.             return (NIL);
  562.         break;
  563.  
  564.         /* check for start of line */
  565.         case '^':
  566.         if (s == _start) {
  567.  
  568.             /* match, be happy */
  569.             matched = 1;
  570.             cs = MNEXT(cs);
  571.         } else if (*cs & ALT) {
  572.  
  573.             /* try the next part */
  574.             matched = 0;
  575.             cs = MNEXT(cs);
  576.         } else if (*cs & OPT) {
  577.  
  578.             /* doesn't matter */
  579.             matched = 1;
  580.             cs = MNEXT(cs);
  581.         } else
  582.  
  583.             /* no match, error return */
  584.             return (NIL);
  585.         break;
  586.  
  587.         /* end of a subexpression, return success */
  588.         case ')':
  589.         return (s);
  590.         }
  591.         break;
  592.     }
  593.     }
  594.     return (s);
  595. }
  596.